//
// Created by 11067 on 2023/3/6.
//
#include "Graph.h"

static Edge edge_buf[MAX_WORD_NUM];
static int edge_buf_p;

Graph::Graph(std::set<std::string> &words) {
    this->words = std::set<std::string>(words);
    init();
}

//Graph::Graph(std::string& str) {
//    str2words(str, words);
//    init();
//}

static bool cmp(Edge* e1, Edge* e2) {
    return e1->word->length() > e2->word->length();
}

void Graph::init() {
    this->op_h = '\0';
    this->op_j = '\0';
    this->op_t = '\0';
    this->is_word = false;

    edge_buf_p = -1;
    std::set<std::string>::iterator it;
    for (it = words.begin(); it != words.end(); it++) {
        edge_buf_p++;
        const std::string *w = &(*it);
        Edge *e = &edge_buf[edge_buf_p];
        e->word = w;
        int begin = (*it)[0] - 'a';
        int end = (*it)[(*it).length() - 1] - 'a';
        e->begin = begin;
        e->end = end;
        e->idx = edge_buf_p;
        nodes[end].words_in.push_back(e);
        nodes[begin].words_out.push_back(e);
        if (begin == end) {
            nodes[begin].cycles.push_back(e);
        }
        edges.push_back(e);
    }
    for (auto & n : nodes) {
        std::sort(n.words_out.begin(), n.words_out.end(), cmp);
    }
    omp_init_lock(&lck);
}

//Graph::~Graph() = default;

bool Graph::has_cycle() {
    int vis[26] = {0};
    int in_deg[26] = {0};
    std::queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (nodes[i].cycles.size() > 1) {
            return true;
        }
        in_deg[i] = (int) nodes[i].words_in.size();
        if (in_deg[i] == 0 && nodes[i].words_out.empty()) {
            vis[i]++;
        } else if (in_deg[i] == 0 || (in_deg[i] == 1 && nodes[i].cycles.size() == 1)) {
            q.push(i);
            vis[i]++;
        }
    }
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (const auto &e: nodes[i].words_out) {
            int j = e->end;
            in_deg[j]--;
            if (j == i) {
                continue;
            }
            if (in_deg[j] == 0 || (in_deg[j] == 1 && nodes[j].cycles.size() == 1)) {
                q.push(j);
                vis[j]++;
            }
        }
    }
    for (int vi: vis) {
        if (vi == 0) {
            return true;
        }
    }
    return false;
}

int Graph::cnt_chains(std::vector<std::vector<const std::string *>> &chains) {
    chains.clear();
    int in_deg[26] = {0};
    std::vector<std::vector<const std::string *>> node_chains[26];
    std::queue<int> q;
    for (int i = 0; i < 26; i++) {
        in_deg[i] = (int) nodes[i].words_in.size();
        if (nodes[i].words_out.empty()) {
            continue;
        }
        if (in_deg[i] == 0 || (in_deg[i] == 1 && nodes[i].cycles.size() == 1)) {
            q.push(i);
        }
    }
    int cnt = 0;
    while (!q.empty() && cnt <= 20001) {
        int i = q.front();
        q.pop();
        if (in_deg[i] == 1 && nodes[i].cycles.size() == 1) {
            int len = (int) node_chains[i].size();
            const std::string *cycle = (*nodes[i].cycles.begin())->word;
            for (int j = 0; j < len; j++) {
                std::vector<const std::string *> t = node_chains[i][j];
                t.push_back(cycle);
                if (t.size() >= 2 && cnt <= 20001) {
                    chains.push_back(t);
                    cnt++;
                }
                node_chains[i].push_back(t);
            }
            std::vector<const std::string *> t;
            t.push_back(cycle);
            node_chains[i].push_back(t);
            in_deg[i] = 0;
        }
        for (const Edge *e: nodes[i].words_out) {
            int j = e->end;
            if (j == i) {
                continue;
            }
            for (const auto &v: node_chains[i]) {
                std::vector<const std::string *> t = v;
                t.push_back(e->word);
                if (t.size() >= 2 && cnt <= 20001) {
                    chains.push_back(t);
                    cnt++;
                }
                node_chains[j].push_back(t);
            }
            std::vector<const std::string *> self;
            self.push_back(e->word);
            node_chains[j].push_back(self);
            in_deg[j] -= 1;
            if ((in_deg[j] == 0 || (in_deg[j] == 1 && nodes[j].cycles.size() == 1)) &&
                !nodes[j].words_out.empty()) {
                q.push(j);
            }
        }
    }
    if (chains.size() > 20000) {
        return -1;
    }
    return 0;
}

void Graph::set_in_deg(int in_deg[]) {
    for (int i = 0; i < 26; i++) {
        in_deg[i] = (int) nodes[i].words_in.size();
    }
    // op_j works. Letter j shouldn't have edges out.
    if (is_lower(op_j)) {
        int i = op_j - 'a';
        for (Edge *e: nodes[i].words_out) {
            in_deg[e->end]--;
        }
    }
    if (!is_lower(op_h)) {
        return;
    }
    // op_h works.
    int can_visit[26] = {false};
    std::queue<int> q;
    q.push(op_h - 'a');
    can_visit[op_h - 'a'] = 1;
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (Edge *e: nodes[i].words_out) {
            int j = e->end;
            if (can_visit[j] == 0) {
                can_visit[j] = 1;
                q.push(j);
            }
        }
    }
    for (int i = 0; i < 26; i++) {
        if (can_visit[i] == 0) {
            for (Edge *e: nodes[i].words_out) {
                int j = e->end;
                in_deg[j]--;
            }
        }
    }
}

int Graph::longest_chain(char op_h, char op_t, char op_j, bool is_word, std::vector<std::string> &chain) {
    chain.clear();
    this->op_h = op_h;
    this->op_t = op_t;
    this->op_j = op_j;
    this->is_word = is_word;

    // if h == j, there's no path
    if (is_lower(op_h) && is_lower(op_j) && op_h == op_j) {
        return 0;
    }

    // init
    const std::string *pred[26];
    int len[26] = {0};
    int in_deg[26] = {0};
    set_in_deg(in_deg);
    for (auto &i: pred) {
        i = nullptr;
    }
    std::queue<int> q;

    if (is_lower(op_h)) {
        q.push(op_h - 'a');
    } else {
        for (int i = 0; i < 26; i++) {
            if (i + 'a' == op_j) {
                continue;
            }
            if (in_deg[i] == 0 && nodes[i].words_out.empty()) {
                continue;
            }
            if (in_deg[i] == 0 || (in_deg[i] == 1 && nodes[i].cycles.size() == 1)) {
                q.push(i);
            }
        }
    }

    // topological sort
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        // letter i has a self-loop.
        if (nodes[i].cycles.size() == 1) {
            len[i] += is_word ? 1 : (int) (*(*nodes[i].cycles.begin())->word).length();
        }
        for (const Edge *e: nodes[i].words_out) {
            int j = e->end;
            if (i == j) {
                continue;
            }
            int new_len = (int) (len[i] + (is_word ? 1 : (*(e->word)).length()));
            if (new_len > len[j]) {
                len[j] = new_len;
                pred[j] = e->word;
            }
            if (j + 'a' == op_j) {
                continue;
            }
            in_deg[j]--;
            if (in_deg[j] == 0 || (in_deg[j] == 1 && nodes[j].cycles.size() == 1)) {
                q.push(j);
            }
        }
    }

    // find the end of the longest chain.
    int max_i = -1; // the chain ends with (max_i + 'a')
    int max_len = 0;
    if (is_lower(op_t)) {
        max_i = op_t - 'a';
    } else {
        for (int i = 0; i < 26; i++) {
            if (len[i] > max_len) {
                max_i = i;
                max_len = len[i];
            }
        }
    }
    if (max_i == -1) {
        return 0;
    }

    // find the longest chain.
    std::vector<const std::string *> rev_chain;
    while (pred[max_i] != nullptr) {
        // if max_i has a self-loop, it should be added to the chain.
        if (nodes[max_i].cycles.size() == 1) {
            const std::string *cycle = (*nodes[max_i].cycles.begin())->word;
            rev_chain.push_back(cycle);
        }
        rev_chain.push_back(pred[max_i]);
        max_i = (*pred[max_i])[0] - 'a';
    }
    // if the header has a self-loop, it should be added to the chain.
    if (nodes[max_i].cycles.size() == 1) {
        const std::string *head = (*nodes[max_i].cycles.begin())->word;
        chain.push_back(*head);
    }
    // reverse the chain.
    for (int i = (int) rev_chain.size() - 1; i >= 0; i--) {
        chain.push_back(*rev_chain[i]);
    }
    if (chain.size() < 2) {
        chain.clear();
    }
    return 0;
}



int Graph::longest_chain_r(char op_h, char op_t, char op_j, bool is_word, std::vector<std::string> &chain) {
    chain.clear();
    memset(dfs_max_len, 0, sizeof (dfs_max_len));
    for (auto &p: dfs_longest_path) {
        p.clear();
    }
    this->op_h = op_h;
    this->op_t = op_t;
    this->op_j = op_j;
    this->is_word = is_word;

    if (is_lower(op_h) && is_lower(op_j) && op_h == op_j) {
        return 0;
    }
//    this->dfs_max_len = 0;
//    std::vector<int> tmp_path[26];
//    for (auto &p: tmp_path) {
//        p.reserve(128);
//    }
    MyStack tmp_path[26];
    IntSet vis[26];
    for (auto &p: tmp_path) {
        p.init(edges.size());
    }
    for (int i = 0; i < 26; ++i) {
        vis[i].init(edges.size());
    }
    if (is_lower(op_h)) {
        dfs_r(op_h - 'a', 0, vis[0], tmp_path[0], 0);
    } else {
        omp_set_num_threads(13);
#pragma omp parallel
        {
            int i = omp_get_thread_num();
            if (i * 2 + 'a' != op_j) {
                dfs_r(2 * i, 0, vis[i * 2], tmp_path[i * 2], 2 * i);
            }
            if (i * 2 + 1 + 'a' != op_j) {
                dfs_r(2 * i + 1, 0, vis[i * 2 + 1], tmp_path[i * 2 + 1], 2 * i + 1);
            }
        }
//        for (int i = 0; i < 26; i++) {
//            if (i + 'a' == op_j) {
//                continue;
//            }
//            tmp_path.clear();
//            vis.clear();
//            dfs_r(i, 0, vis, tmp_path);
//        }
    }
    for (int i = 0; i < 26; ++i) {
        vis[i].dispose();
        tmp_path[i].dispose();
    }
    int max_path_idx = 0;
    int max_len = dfs_max_len[0];
    for (int i = 1; i < 26; ++i) {
        if (dfs_max_len[i] > max_len) {
            max_path_idx = i;
            max_len =dfs_max_len[i];
        }
    }
    for (int x: dfs_longest_path[max_path_idx]) {
        chain.push_back(*edges[x]->word);
    }
    if (chain.size() < 2) {
        chain.clear();
    }
    return 0;
}

typedef Edge* EdgeSet[26];
void Graph::dfs_r(int i, int now_len, IntSet vis, MyStack &path, int t_id) {
    bool has_next = false;
    if (i + 'a' != op_j) {
        //auto *letters = reinterpret_cast<EdgeSet *>(new Edge *[27]);
        EdgeSet letters;
        memset(letters, 0, sizeof(Edge*)*26);
        for (Edge* e: nodes[i].words_out) {
            if (vis.count(e->idx) == 0 && letters[e->end] == nullptr) {
                letters[e->end] = e;
            }
        }
        for (auto p : letters) {
            if (p == nullptr) {
                continue;
            }
            Edge* e = p;
            has_next = true;
            vis.insert(e->idx);
            path.push_back(e->idx);
            int edge_len = is_word ? 1 : (int) e->word->length();
            dfs_r(e->end, now_len + edge_len, vis, path, t_id);
            path.pop_back();
            vis.erase(e->idx);
        }
        //delete [] letters;
//        for (Edge *e: nodes[i].words_out) {
//            if (vis.count(e->idx) == 0) {
//                has_next = true;
//                vis.insert(e->idx);
//                path.push_back(e->idx);
//                int edge_len = is_word ? 1 : (int) e->word->length();
//                dfs_r(e->end, now_len + edge_len, vis, path);
//                path.pop_back();
//                vis.erase(e->idx);
//            }
//        }
    }
    //omp_set_lock(&lck);
    if (is_lower(op_t)) {
        if (i + 'a' == op_t && now_len > this->dfs_max_len[t_id]) {
//            omp_set_lock(&lck);
            this->dfs_max_len[t_id] = now_len;
//            this->dfs_longest_path = path;
            path.copy_into(this->dfs_longest_path[t_id]);
//            omp_unset_lock(&lck);
        }
    } else if (!has_next && now_len > this->dfs_max_len[t_id]) {
//        omp_set_lock(&lck);
        this->dfs_max_len[t_id] = now_len;
//        this->dfs_longest_path = path;
        path.copy_into(this->dfs_longest_path[t_id]);
//        omp_unset_lock(&lck);
    }
    //omp_unset_lock(&lck);
}
